package com.company.笔试.二叉树遍历;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;

/**
 * @ClassName ThreeTreeOrders
 * @Description TODO
 * @Author 11
 * @Date 2021/6/6 20:06
 * @Version 1.0
 */
class TreeNode{
    int val;
    TreeNode leftNode=null;
    TreeNode rightNode=null;


    public TreeNode(int val) {
        this.val = val;
    }
}



public class ThreeTreeOrders {
    //前中后序存储数组
    public ArrayList<Integer> firstList = new ArrayList<>();
    public ArrayList<Integer> midList = new ArrayList<>();
    public ArrayList<Integer> lastList = new ArrayList<>();


    public int[][] threeOrders (TreeNode root) {
        // write code here
        firstOrders(root);
        middleOrder(root);
        lastOrder(root);
        int [][] res = new int[3][firstList.size()];
        res[0] = firstList.stream().mapToInt(Integer::intValue).toArray();
        res[1] = midList.stream().mapToInt(Integer::intValue).toArray();
        res[2] = lastList.stream().mapToInt(Integer::intValue).toArray();
        return res;
    }

    public void firstOrders(TreeNode treeNode){
        if (treeNode ==null){
            return;
        }
        firstList.add(treeNode.val);
        firstOrders(treeNode.leftNode);
        firstOrders(treeNode.rightNode);


    }
    //中序遍历
    public void middleOrder(TreeNode root){
        //跳出条件
        if(root==null){
            return;
        }
        middleOrder(root.leftNode);
        midList.add(root.val);
        middleOrder(root.rightNode);

    }

    //后序遍历
    public void lastOrder(TreeNode root){
        //跳出条件
        if(root==null){
            return;
        }
        lastOrder(root.leftNode);
        lastOrder(root.rightNode);
        lastList.add(root.val);
    }

    //层序遍历 队列解法
    public ArrayList<ArrayList<Integer>> levelOrder (TreeNode root) {
        // write code here
        ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
        if (root==null){
            return res;
        }
        Queue<TreeNode> queue = new LinkedList<>();

        queue.add(root);
        while (!queue.isEmpty()){
            ArrayList<Integer> list= new ArrayList<>();
            int size = queue.size();
            while (size >0){
                TreeNode curNode = queue.poll();
                list.add(curNode.val);
                if (curNode.leftNode!=null){
                    queue.offer(curNode.leftNode);
                }
                if (curNode.rightNode!=null){
                    queue.offer(curNode.rightNode);
                }
                size--;

            }
            res.add(list);

        }
        return res;
    }

    //DFS解法
    public ArrayList<ArrayList<Integer>> levelOrder2 (TreeNode root) {
        ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
        if (root==null){
            return res;
        }
        DFS(root,res,0);
        return res;

    }

    private void DFS(TreeNode root, ArrayList<ArrayList<Integer>> res, int depth) {
        if (root==null){
            return ;
        }
        if (res.size()==depth) res.add(new ArrayList<>());

        DFS(root.leftNode,res,depth+1);
        res.get(depth).add(root.val);
        DFS(root.rightNode,res,depth+1);

    }


}
